#include <iostream>

using namespace std;

struct node
{
	int value;
	struct node *left;
	struct node *right;
};

void FindPath(struct node *root, int sum)
{
	struct node *stack[10];
	int flag[10];
	int top = 0;

	stack[0] = root;
	sum -= root->value;
	flag[top] = 0;
	while(true)
	{
		//cout<<top<<" "<<stack[top]->value<<"  "<<flag[top]<<endl;
		if(top == -1)
			break;
		if(sum == 0 && stack[top]->left == NULL && stack[top]->right == NULL)
		{
			for(int i = 0; i <= top; i++)
				cout<<stack[i]->value<<" ";
			cout<<endl;
		}
		if(flag[top] == 0 && stack[top]->left != NULL)
		{
			flag[top + 1] = 0;
			flag[top]++;
			stack[top + 1] = stack[top++]->left;
			sum -= stack[top]->value;
		}
		else if(flag[top] == 1 && stack[top]->right != NULL)
		{
			flag[top]++;
			flag[top + 1] = 0;
			stack[top + 1] = stack[top++]->right;
			sum -= stack[top]->value;
		}
		else if(flag[top] == 0 && stack[top]->left == NULL && stack[top]->right == NULL || flag[top] == 2)
		{
			sum += stack[top]->value;
			top--;
		}
	}
}

int main()
{
	struct node a10, a5, a12, a4, a7;
	
	a10.left = &a5;
	a10.right = &a12;
	a10.value = 10;

	a5.left = &a4;
	a5.right = &a7;
	a5.value = 5;

	a12.left = NULL;
	a12.right = NULL;
	a12.value = 12;

	a4.left = NULL;
	a4.right = NULL;
	a4.value = 4;

	a7.left = NULL;
	a7.right = NULL;
	a7.value = 7;

	FindPath(&a10, 19);
}
